{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Create Components With Same Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #array #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #数组 #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: componentValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #创建价值相同的连通块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一棵&nbsp;<code>n</code>&nbsp;个节点的无向树，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，其中&nbsp;<code>nums[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个节点的值。同时给你一个长度为 <code>n - 1</code>&nbsp;的二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示节点&nbsp;<code>a<sub>i</sub></code>&nbsp;与&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条边。</p>\n",
    "\n",
    "<p>你可以 <strong>删除</strong>&nbsp;一些边，将这棵树分成几个连通块。一个连通块的 <strong>价值</strong>&nbsp;定义为这个连通块中 <strong>所有</strong> 节点 <code>i</code>&nbsp;对应的 <code>nums[i]</code>&nbsp;之和。</p>\n",
    "\n",
    "<p>你需要删除一些边，删除后得到的各个连通块的价值都相等。请返回你可以删除的边数&nbsp;<strong>最多</strong>&nbsp;为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/08/26/diagramdrawio.png\" style=\"width: 441px; height: 351px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] \n",
    "<b>输出：</b>2 \n",
    "<b>解释：</b>上图展示了我们可以删除边 [0,1] 和 [3,4] 。得到的连通块为 [0] ，[1,2,3] 和 [4] 。每个连通块的价值都为 6 。可以证明没有别的更好的删除方案存在了，所以答案为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2], edges = []\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有任何边可以删除。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 50</code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= edges[i][0], edges[i][1] &lt;= n - 1</code></li>\n",
    "\t<li><code>edges</code>&nbsp;表示一棵合法的树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [create-components-with-same-value](https://leetcode.cn/problems/create-components-with-same-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [create-components-with-same-value](https://leetcode.cn/problems/create-components-with-same-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,2,2,2,6]\\n[[0,1],[1,2],[1,3],[3,4]]', '[2]\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_all_factor(num):\n",
    "    # 获取整数所有的因子包括 1 和它自己\n",
    "    factor = set()\n",
    "    for i in range(1, int(math.sqrt(num)) + 1):\n",
    "        if num % i == 0:\n",
    "            factor.add(i)\n",
    "            factor.add(num // i)\n",
    "    return sorted(list(factor))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "\n",
    "        s = sum(nums)\n",
    "        factor = get_all_factor(s)\n",
    "        for f in factor:\n",
    "            sub = [0]*n\n",
    "            stack = [[0, -1]]\n",
    "            cnt = 0\n",
    "            while stack:\n",
    "                i, fa = stack.pop()\n",
    "                if i >= 0:\n",
    "                    stack.append([~i, fa])\n",
    "                    for j in dct[i]:\n",
    "                        if j != fa:\n",
    "                            stack.append([j, i])\n",
    "                else:\n",
    "                    i = ~i\n",
    "                    x = nums[i]\n",
    "                    for j in dct[i]:\n",
    "                        if j != fa:\n",
    "                            x += sub[j]\n",
    "                    if x == f:\n",
    "                        x = 0\n",
    "                        cnt += 1\n",
    "                    sub[i] = x\n",
    "            if cnt == s // f:\n",
    "                return s//f-1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        def myfun1(my_dict,value,nums1,my_mat,one_mat):\n",
    "            result=0\n",
    "            while one_mat:\n",
    "                now_index=one_mat.pop(0)\n",
    "                if nums1[now_index]>value:\n",
    "                    return -1\n",
    "                elif nums1[now_index]==value:\n",
    "                    next_index_mat=list(my_dict[now_index].keys())\n",
    "                    if next_index_mat:\n",
    "                        next_index=next_index_mat[0]\n",
    "                        del my_dict[next_index][now_index]\n",
    "                        if len(my_dict[next_index])<=1 and my_mat[next_index]==0:\n",
    "                            one_mat.append(next_index)\n",
    "                            my_mat[next_index]=1\n",
    "                        result+=1\n",
    "                else:\n",
    "                    next_index_mat=list(my_dict[now_index].keys())\n",
    "                    if next_index_mat:\n",
    "                       next_index=next_index_mat[0] \n",
    "                       nums1[next_index]+=nums1[now_index]\n",
    "                       del my_dict[next_index][now_index]\n",
    "                       if len(my_dict[next_index])<=1 and my_mat[next_index]==0:\n",
    "                            one_mat.append(next_index)\n",
    "                            my_mat[next_index]=1\n",
    "                    else:\n",
    "                        return -1\n",
    "\n",
    "            return result        \n",
    "\n",
    "        my_dict={}\n",
    "        for i,j in edges:\n",
    "            if i not in my_dict:\n",
    "                my_dict[i]={}\n",
    "            my_dict[i][j]=1\n",
    "            if j not in my_dict:\n",
    "                my_dict[j]={}\n",
    "            my_dict[j][i]=1\n",
    "\n",
    "        sum1=0\n",
    "        for i in nums:\n",
    "            sum1+=i\n",
    "        max1=max(nums)\n",
    "\n",
    "        result=0\n",
    "\n",
    "        my_mat=[0]*len(my_dict)\n",
    "        one_mat=[]\n",
    "        for key1,value1 in my_dict.items():\n",
    "            if len(value1)==1:\n",
    "                one_mat.append(key1)\n",
    "                my_mat[key1]=1 \n",
    "\n",
    "        left=max1\n",
    "        right=sum1       \n",
    "        if len(one_mat)==len(my_dict)-1:\n",
    "            left=max1\n",
    "            right=max1+1\n",
    "        for i in range(left,right):\n",
    "            if sum1%i==0:\n",
    "                b=copy.deepcopy(my_dict)\n",
    "                temp_result=myfun1(b,i,nums[:],my_mat[:],one_mat[:])\n",
    "                if temp_result!=-1:\n",
    "                    result=max(result,temp_result)\n",
    "                    return result\n",
    "\n",
    "        return result\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        if len(nums) == sum(nums): return len(nums)-1\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(x,pa,val):\n",
    "            s = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y == pa: continue\n",
    "                t = dfs(y,x,val)\n",
    "                if t == -1: return -1\n",
    "                s += t\n",
    "            if s > val: return -1\n",
    "            return s%val\n",
    "        \n",
    "        ss = sum(nums)\n",
    "        ans = 0\n",
    "        for p in range(2,(ss//2)+1):\n",
    "            if ss % p != 0: continue\n",
    "            if dfs(0,-1,p) == -1: continue\n",
    "            ans = max(ans,ss//p-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        if len(nums) == sum(nums): return len(nums)-1\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(x,pa,val):\n",
    "            s = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y == pa: continue\n",
    "                t = dfs(y,x,val)\n",
    "                if t == -1: return -1\n",
    "                s += t\n",
    "            if s > val: return -1\n",
    "            return s%val\n",
    "        \n",
    "        ss = sum(nums)\n",
    "        ans = 0\n",
    "        for p in range(2,(ss//2)+1):\n",
    "            if ss % p != 0: continue\n",
    "            if dfs(0,-1,p) == -1: continue\n",
    "            ans = max(ans,ss//p-1)\n",
    "            break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "\n",
    "        def dfs(x, fa):\n",
    "            v = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    u = dfs(y, x)\n",
    "                    v += u\n",
    "                    if u < 0:\n",
    "                        return -1\n",
    "            if v == t:\n",
    "                return 0\n",
    "            if v > t:\n",
    "                return -1\n",
    "            return v\n",
    "        \n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s % (i + 1) == 0:\n",
    "                t = s // (i + 1)\n",
    "                if dfs(0, -1) == 0:\n",
    "                    return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        s = sum(nums)\n",
    "        mx = max(nums)\n",
    "\n",
    "        for num in range(mx, s + 1):\n",
    "            if s % num != 0:\n",
    "                continue\n",
    "            if s // num > n:\n",
    "                continue\n",
    "\n",
    "            def dfs(x: int, fa: int):\n",
    "                s = nums[x]\n",
    "                for y in g[x]:\n",
    "                    if y == fa:\n",
    "                        continue\n",
    "                    sub = dfs(y, x)\n",
    "                    if sub == num:\n",
    "                        continue\n",
    "                    if sub == inf:\n",
    "                        return inf\n",
    "                    s += sub\n",
    "                if s > num:\n",
    "                    return inf\n",
    "                return s\n",
    "\n",
    "            if dfs(0, -1) != inf:\n",
    "                # print(num, dfs(0, -1))\n",
    "                return s // num - 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        _min, _max, total = float('inf'), float('-inf'), 0\n",
    "        for x in nums:\n",
    "            total += x\n",
    "            _min = min(_min, x)\n",
    "            _max = max(_max, x)\n",
    "        if _min == _max:\n",
    "            return n - 1\n",
    "        nexts = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            nexts[a].append(b)\n",
    "            nexts[b].append(a)\n",
    "        def dfs(who, parent, partSum):\n",
    "            whoSum = nums[who]\n",
    "            for nex in nexts[who]:\n",
    "                if nex == parent: continue\n",
    "                fastFail, remSum = dfs(nex, who, partSum)\n",
    "                if fastFail: return True, 0\n",
    "                whoSum += remSum\n",
    "                if whoSum > partSum: \n",
    "                    return True, 0\n",
    "            if whoSum == partSum:\n",
    "                whoSum = 0\n",
    "            return False, whoSum\n",
    "        for parts in range(n-1, 1, -1):\n",
    "            partSum, r = divmod(total, parts)\n",
    "            if r: continue\n",
    "            fastFail, r =  dfs(0, -1, partSum)\n",
    "            if fastFail or r: continue\n",
    "            return parts - 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        # 枚举因子，DFS连通块\n",
    "        n = len(nums)\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x, fa):\n",
    "            s = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res == -1:\n",
    "                        return -1\n",
    "                    s += res\n",
    "            if s > target:\n",
    "                return -1\n",
    "            if s == target:\n",
    "                return 0\n",
    "            return s\n",
    "\n",
    "        total = sum(nums)\n",
    "        # for i in range(n, 0, -1):\n",
    "        for i in range(max(n, total//max(nums)), 0, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0:\n",
    "                    return i-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        e = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        # 返回节点u向下的子树删除了所有合法连通块后的节点之和\n",
    "        def dfs(u,fa):\n",
    "            s = nums[u]\n",
    "            for j in e[u]:\n",
    "                if j!=fa:\n",
    "                    s += dfs(j,u)\n",
    "            # 自底向上\n",
    "            # 如果和是target，就把这一棵子树删除\n",
    "            if s == target:\n",
    "                return 0\n",
    "            return s\n",
    "        \n",
    "        total = sum(nums)\n",
    "        # 枚举连通块的个数\n",
    "        for i in range(n,0,-1):\n",
    "            if total%i==0:\n",
    "                target = total//i # 每个连通块的价值\n",
    "                # 如果整棵树向下的节点和是0：删除了所有合法连通块后就是答案\n",
    "                if dfs(0,-1)==0:\n",
    "                    return i-1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        # 枚举因子，DFS连通块\n",
    "        n = len(nums)\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x, fa):\n",
    "            s = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res == -1:\n",
    "                        return -1\n",
    "                    s += res\n",
    "            if s > target:\n",
    "                return -1\n",
    "            if s == target:\n",
    "                return 0\n",
    "            return s\n",
    "\n",
    "        total = sum(nums)\n",
    "        for i in range(n, 0, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0:\n",
    "                    return i-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "\n",
    "        def dfs(x:int,fa:int) -> int:\n",
    "            s = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y,x)\n",
    "                    if res == -1: return -1\n",
    "                    s += res\n",
    "            if s > target:\n",
    "                return -1\n",
    "            if s == target:\n",
    "                return 0\n",
    "            return s\n",
    "        total = sum(nums)\n",
    "        for i in range(n, 0, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0,-1) == 0:\n",
    "                    return i - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        s = sum(nums)\n",
    "        mx = max(nums)\n",
    "\n",
    "        for num in range(mx, s + 1):\n",
    "            if s % num != 0:\n",
    "                continue\n",
    "            if s // num > n:\n",
    "                continue\n",
    "\n",
    "            def dfs(x: int, fa: int):\n",
    "                s = nums[x]\n",
    "                for y in g[x]:\n",
    "                    if y == fa:\n",
    "                        continue\n",
    "                    sub = dfs(y, x)\n",
    "                    if sub == num:\n",
    "                        continue\n",
    "                    s += sub\n",
    "                if s > num:\n",
    "                    return inf\n",
    "                return s\n",
    "\n",
    "            if dfs(0, -1) != inf:\n",
    "                # print(num, dfs(0, -1))\n",
    "                return s // num - 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e1, e2 in edges:\n",
    "            g[e1].append(e2)\n",
    "            g[e2].append(e1)\n",
    "        s = sum(nums)\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        def f(x, fa,target):\n",
    "            sx = nums[x]\n",
    "            for nex in g[x]:\n",
    "                if nex != fa:\n",
    "                    snex = f(nex, x, target)\n",
    "                    if snex == target:\n",
    "                        snex = 0\n",
    "                    sx += snex\n",
    "            return sx\n",
    "\n",
    "\n",
    "\n",
    "        for kuai in range(n , 0, -1):\n",
    "            if s % kuai == 0:\n",
    "                target = s // kuai\n",
    "                if f(0, -1, target) == target: return kuai - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n=len(nums)\n",
    "        ss=sum(nums)\n",
    "        g=[[] for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        ans=0\n",
    "        temp=0\n",
    "        def help(x,fa,s):\n",
    "            nonlocal temp\n",
    "            res=nums[x]\n",
    "            for i in g[x]:\n",
    "                if i!=fa:\n",
    "                    res+=help(i,x,s)\n",
    "            if res==s:\n",
    "                temp+=1\n",
    "                res=0\n",
    "            return res\n",
    "        for i in range(1,ss+1):\n",
    "            if ss%i==0:\n",
    "                temp=0\n",
    "                res=help(0,0,i)\n",
    "                if res==0:\n",
    "                    ans=max(ans,temp-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def factors(x):\n",
    "    f = []\n",
    "    for i in range(1, int(math.sqrt(x))+1):\n",
    "        if x % i == 0:\n",
    "            f.append(i)\n",
    "            if i*i != x:\n",
    "                f.append(x//i)\n",
    "    return f\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        G = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "\n",
    "        # s = sum(nums)\n",
    "        # a = set(factors(s))\n",
    "        # c = Counter()\n",
    "        # def dfs(i, p):\n",
    "        #     x = nums[i]\n",
    "        #     for j in G[i]:\n",
    "        #         if j == p: continue\n",
    "        #         x += dfs(j, i)\n",
    "        #     for k in factors(x):\n",
    "        #         if k in a:\n",
    "        #             c[k] += 1\n",
    "        #     return x\n",
    "        # dfs(0, -1)\n",
    "        # ans = 1\n",
    "        # for i in c:\n",
    "        #     if i * c[i] == s:\n",
    "        #         ans = max(ans, c[i])\n",
    "        # return ans-1\n",
    "\n",
    "        g = [0] * n\n",
    "        def dfs(i, p):\n",
    "            g[i] = nums[i]\n",
    "            for j in G[i]:\n",
    "                if j == p: continue\n",
    "                dfs(j, i)\n",
    "                g[i] += g[j]\n",
    "\n",
    "        dfs(0, -1)\n",
    "        ans = 1\n",
    "        for i in sorted(factors(g[0])):\n",
    "            k = sum(g[j] % i == 0 for j in range(n))\n",
    "            if k * i == g[0]:\n",
    "                return k-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        target = 0\n",
    "        def dfs(x, fa):\n",
    "            s = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res == -1:\n",
    "                        return -1\n",
    "                    s += res\n",
    "            if s > target:\n",
    "                return -1\n",
    "            if s == target:\n",
    "                return 0\n",
    "            return s\n",
    "        dfs(0, -1)\n",
    "\n",
    "        total = sum(nums)\n",
    "        for i in range(n, 0, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0:\n",
    "                    return i-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        total = sum(nums)\n",
    "        max1 = max(nums)\n",
    "        plist = []\n",
    "        for i in range(max1, total+1):\n",
    "            if total % i == 0:\n",
    "                plist.append(i)\n",
    "        m1 = defaultdict(list)\n",
    "        for i in edges:\n",
    "            m1[i[0]].append(i[1])\n",
    "            m1[i[1]].append(i[0])\n",
    "\n",
    "        def get_min_cnt(start, prev, target):\n",
    "            cnt = nums[start]\n",
    "            for i in m1[start]:\n",
    "                if i != prev:\n",
    "                    cnt += get_min_cnt(i, start, target)\n",
    "            if cnt == target:\n",
    "                return 0\n",
    "            return cnt\n",
    "\n",
    "        for i in plist:\n",
    "            ans = get_min_cnt(0, -1 , i)\n",
    "            if ans == 0:\n",
    "                return total//i - 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        total = sum(nums)\n",
    "        max1 = max(nums)\n",
    "        plist = []\n",
    "        for i in range(max1, total+1):\n",
    "            if total % i == 0:\n",
    "                plist.append(i)\n",
    "        m1 = defaultdict(list)\n",
    "        for i in edges:\n",
    "            m1[i[0]].append(i[1])\n",
    "            m1[i[1]].append(i[0])\n",
    "\n",
    "        def get_min_cnt(start, prev, target):\n",
    "            cnt = nums[start]\n",
    "            for i in m1[start]:\n",
    "                if i != prev:\n",
    "                    cnt += get_min_cnt(i, start, target)\n",
    "            if cnt == target:\n",
    "                return 0\n",
    "            return cnt\n",
    "\n",
    "        for i in plist:\n",
    "            ans = get_min_cnt(0, -1 , i)\n",
    "            if ans == 0:\n",
    "                return total//i - 1\n",
    "        return 0\n",
    "\n",
    "a = Solution()\n",
    "print(a.componentValue(nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, a: List[int], e: List[List[int]]) -> int:\n",
    "        n=len(a)\n",
    "        tree=[[] for i in range(n)]\n",
    "        for i,j in e:\n",
    "            tree[i].append(j)\n",
    "            tree[j].append(i)\n",
    "        ans=0\n",
    "        s=sum(a)\n",
    "        def dfs(r,f,v):\n",
    "            t=[]\n",
    "            for i in tree[r]:\n",
    "                if i!=f:\n",
    "                    u,res=dfs(i,r,v)\n",
    "                    if not res:\n",
    "                        return -1,False\n",
    "                    if u!=v and u!=0:\n",
    "                        t.append(u)\n",
    "            if len(t)>1:\n",
    "                if sum(t)+a[r]==v:\n",
    "                    return 0,True\n",
    "                else:\n",
    "                    return -1,False\n",
    "            elif len(t)==1:\n",
    "                if t[0]+a[r]==v:\n",
    "                    return 0,True\n",
    "                elif t[0]+a[r]>v:\n",
    "                    return -1,False\n",
    "                else:\n",
    "                    return t[0]+a[r],True\n",
    "            else:\n",
    "                if a[r]==v:\n",
    "                    return 0,True\n",
    "                elif a[r]>v:\n",
    "                    return -1,False\n",
    "                else:\n",
    "                    return a[r],True\n",
    "        for i in range(2,n+1):\n",
    "            if s%i==0:\n",
    "                u,res=dfs(0,-1,s//i)\n",
    "                if res and (u==0 or u==s//i):\n",
    "                    ans=i-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, a: List[int], e: List[List[int]]) -> int:\n",
    "        n=len(a)\n",
    "        tree=[[] for i in range(n)]\n",
    "        for i,j in e:\n",
    "            tree[i].append(j)\n",
    "            tree[j].append(i)\n",
    "        ans=0\n",
    "        s=sum(a)\n",
    "        def dfs(r,f,v):\n",
    "            t=[]\n",
    "            for i in tree[r]:\n",
    "                if i!=f:\n",
    "                    u,res=dfs(i,r,v)\n",
    "                    if not res:\n",
    "                        return -1,False\n",
    "                    if u!=v and u!=0:\n",
    "                        t.append(u)\n",
    "            if len(t)>1:\n",
    "                if sum(t)+a[r]==v:\n",
    "                    return 0,True\n",
    "                else:\n",
    "                    return -1,False\n",
    "            elif len(t)==1:\n",
    "                if t[0]+a[r]==v:\n",
    "                    return 0,True\n",
    "                elif t[0]+a[r]>v:\n",
    "                    return -1,False\n",
    "                else:\n",
    "                    return t[0]+a[r],True\n",
    "            else:\n",
    "                if a[r]==v:\n",
    "                    return 0,True\n",
    "                elif a[r]>v:\n",
    "                    return -1,False\n",
    "                else:\n",
    "                    return a[r],True\n",
    "        for i in range(2,n+1):\n",
    "            if s%i==0:\n",
    "                u,res=dfs(0,-1,s//i)\n",
    "                if res and (u==0 or u==s//i):\n",
    "                    ans=i-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\r\n",
    "        g = [[] for _ in nums]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)\r\n",
    "\r\n",
    "        def dfs(x: int, fa: int) -> int:\r\n",
    "            s = nums[x]  # 价值\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa:\r\n",
    "                    res = dfs(y, x)\r\n",
    "                    if res < 0: return -1\r\n",
    "                    s += res\r\n",
    "            if s > target: return -1\r\n",
    "            return s if s < target else 0\r\n",
    "\r\n",
    "        total = sum(nums)\r\n",
    "        for i in range(total // max(nums), 1, -1):\r\n",
    "            if total % i == 0:\r\n",
    "                target = total // i\r\n",
    "                if dfs(0, -1) == 0: return i - 1\r\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in nums]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "            s = nums[x]  # 价值\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res < 0: return -1\n",
    "                    s += res\n",
    "            if s > target: return -1\n",
    "            return s if s < target else 0\n",
    "\n",
    "        total = sum(nums)\n",
    "        for i in range(total // max(nums), 1, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0: return i - 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        # 建图\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        # 求节点的价值总和s、节点最大价值mx，由于分块的价值肯定不小于mx，也即分块数肯定不会大于s / mx，所以可以从s / mx开始降序枚举分块数\n",
    "        s = sum(nums)\n",
    "        mx = max(nums)\n",
    "\n",
    "        target = 0\n",
    "\n",
    "        def dfs(u: int, fa: int) -> int:\n",
    "            res = nums[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    tmp = dfs(v, u)\n",
    "                    if tmp < 0:  # 无效\n",
    "                        return -1\n",
    "                    res += tmp\n",
    "            if res > target:  # 无效\n",
    "                return -1\n",
    "            return res if res < target else 0\n",
    "\n",
    "        for i in range(s // mx, 1, -1):\n",
    "            if s % i == 0:  # 数值上可以恰好分为i块，还需要根据实际图形判断是否可以分为i块的每块target = s / i大小\n",
    "                target = s // i\n",
    "                if dfs(0, -1) == 0:  # dfs检查后发现可以分为每块target = s / i价值，由于i是倒序枚举的，第一个满足的i就是最大的i，可以直接返回删边次数i - 1\n",
    "                    return i - 1\n",
    "\n",
    "        # 否则肯定可以将整棵树看成一个整体，删除边的次数为零\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\r\n",
    "        g = [[] for _ in nums]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)\r\n",
    "\r\n",
    "        def dfs(x: int, fa: int) -> int:\r\n",
    "            s = nums[x]\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa:\r\n",
    "                    res = dfs(y, x)\r\n",
    "                    if res < 0:\r\n",
    "                        return -1\r\n",
    "                    s += res\r\n",
    "            if s > target:\r\n",
    "                return -1\r\n",
    "            return s if s < target else 0\r\n",
    "\r\n",
    "        total = sum(nums)\r\n",
    "        for i in range(total // max(nums), 1, -1):\r\n",
    "            if total % i == 0:\r\n",
    "                target = total // i\r\n",
    "                if (dfs(0, -1)) == 0:\r\n",
    "                    return i-1\r\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        def check(node, par, target):\n",
    "            cursum = nums[node]\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                nxt = check(nei, node, target)\n",
    "                if nxt == - 1:\n",
    "                    return - 1 \n",
    "                cursum += nxt \n",
    "            if cursum == target:\n",
    "                return 0\n",
    "            if cursum > target:\n",
    "                return - 1 \n",
    "            return cursum\n",
    "        s = sum(nums)\n",
    "        for i in range(1, s + 1):\n",
    "            if s % i:\n",
    "                continue \n",
    "            if check(0, - 1, i) == 0:\n",
    "                return s // i - 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        \n",
    "        # Create graph representation\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        # Find divisors of a number\n",
    "        def divisors(n):\n",
    "            result = []\n",
    "            for i in range(1, int(n**0.5) + 1):\n",
    "                if n % i == 0:\n",
    "                    result.append(i)\n",
    "                    if i != n // i:\n",
    "                        result.append(n // i)\n",
    "            return result\n",
    "        \n",
    "        # DFS function to calculate sums of subtrees\n",
    "        def dfs(node, parent, target):\n",
    "            val = nums[node]\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor != parent:\n",
    "                    res = dfs(neighbor, node, target)\n",
    "                    if res == -1: # not possible to divide subtree\n",
    "                        return -1\n",
    "                    val += res\n",
    "            if val == target:\n",
    "                return 0\n",
    "            return val\n",
    "        \n",
    "        # Calculate the total value of the tree\n",
    "        total_val = sum(nums)\n",
    "        \n",
    "        # Find all divisors of the total value\n",
    "        possible_vals = divisors(total_val)\n",
    "        \n",
    "        max_parts = 0\n",
    "        for val in possible_vals:\n",
    "            if dfs(0, -1, val) == 0:\n",
    "                max_parts = max(max_parts, total_val // val)\n",
    "                \n",
    "        # return the maximum number of deletable edges\n",
    "        return max_parts - 1 if max_parts > 0 else 0\n",
    "\n",
    "# Test\n",
    "solution = Solution()\n",
    "print(solution.componentValue([6,2,2,2,6], [[0,1],[1,2],[1,3],[3,4]])) # Expected output: 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        \n",
    "        # Create graph representation\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        # Find divisors of a number\n",
    "        def divisors(n):\n",
    "            result = []\n",
    "            for i in range(1, int(n**0.5) + 1):\n",
    "                if n % i == 0:\n",
    "                    result.append(i)\n",
    "                    if i != n // i:\n",
    "                        result.append(n // i)\n",
    "            return result\n",
    "        \n",
    "        # DFS function to calculate sums of subtrees\n",
    "        def dfs(node, parent, target):\n",
    "            val = nums[node]\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor != parent:\n",
    "                    res = dfs(neighbor, node, target)\n",
    "                    if res == -1: # not possible to divide subtree\n",
    "                        return -1\n",
    "                    val += res\n",
    "            if val == target:\n",
    "                return 0\n",
    "            return val\n",
    "        \n",
    "        # Calculate the total value of the tree\n",
    "        total_val = sum(nums)\n",
    "        \n",
    "        # Find all divisors of the total value\n",
    "        possible_vals = divisors(total_val)\n",
    "        \n",
    "        max_parts = 0\n",
    "        for val in possible_vals:\n",
    "            if dfs(0, -1, val) == 0:\n",
    "                max_parts = max(max_parts, total_val // val)\n",
    "                \n",
    "        # return the maximum number of deletable edges\n",
    "        return max_parts - 1 if max_parts > 0 else 0\n",
    "\n",
    "# Test\n",
    "solution = Solution()\n",
    "print(solution.componentValue([6,2,2,2,6], [[0,1],[1,2],[1,3],[3,4]])) # Expected output: 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in nums]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "            s = nums[x]  # 价值\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res < 0: return -1\n",
    "                    s += res\n",
    "            if s > target: return -1\n",
    "            return s if s < target else 0\n",
    "\n",
    "        total = sum(nums)\n",
    "        for i in range(total // max(nums), 1, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0: return i - 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in nums]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x,fa)->int:\n",
    "            s=nums[x]\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    res=dfs(y,x)\n",
    "                    if res<0:return -1\n",
    "                    s+=res\n",
    "            if s>target:return -1\n",
    "            return s if s<target else 0\n",
    "        total=sum(nums)\n",
    "        for i in range(total // max(nums), 1, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0: return i - 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in nums]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "            s = nums[x]  # 价值\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res < 0: return -1\n",
    "                    s += res\n",
    "            if s > target: return -1\n",
    "            return s if s < target else 0\n",
    "\n",
    "        total = sum(nums)\n",
    "        for i in range(total // max(nums), 1, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0: return i - 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in nums]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "            s = nums[x]  # 价值\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res < 0: return -1\n",
    "                    s += res\n",
    "            if s > target: return -1\n",
    "            return s if s < target else 0\n",
    "\n",
    "        total = sum(nums)\n",
    "        for i in range(total // max(nums), 1, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0: return i - 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        g = [[] for _ in nums]\n",
    "\n",
    "        for x, y in edges:\n",
    "\n",
    "            g[x].append(y)\n",
    "\n",
    "            g[y].append(x)\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "\n",
    "            s = nums[x]  # 价值\n",
    "\n",
    "            for y in g[x]:\n",
    "\n",
    "                if y != fa:\n",
    "\n",
    "                    res = dfs(y, x)\n",
    "\n",
    "                    if res < 0: return -1\n",
    "\n",
    "                    s += res\n",
    "\n",
    "            if s > target: return -1\n",
    "\n",
    "            return s if s < target else 0\n",
    "\n",
    "\n",
    "\n",
    "        total = sum(nums)\n",
    "\n",
    "        for i in range(total // max(nums), 1, -1):\n",
    "\n",
    "            if total % i == 0:\n",
    "\n",
    "                target = total // i\n",
    "\n",
    "                if dfs(0, -1) == 0: return i - 1\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        e = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        scores = [0] * n\n",
    "        def dfs(node, pn):\n",
    "            for ne in e[node]:\n",
    "                if ne == pn: continue\n",
    "                scores[node] += dfs(ne, node)\n",
    "            scores[node] += nums[node]\n",
    "            return scores[node]\n",
    "        dfs(0, -1)\n",
    "        # print(scores)\n",
    "        # vals = set(scores)\n",
    "        \n",
    "        # def dfs1(node, pn):\n",
    "        #     for ne in e[node]:\n",
    "        #         if ne == pn: continue\n",
    "        #         scores[node] += dfs(ne, node)\n",
    "        #     scores[node] += nums[node]\n",
    "        #     return scores[node]\n",
    "        su = scores[0]\n",
    "        for i in range(n, 1, -1):\n",
    "            cnt = 0\n",
    "            if su % i == 0:\n",
    "                each = su // i\n",
    "                for j in range(n):\n",
    "                    if scores[j] % each == 0:\n",
    "                        cnt += 1\n",
    "                if cnt >= i:\n",
    "                    return i - 1\n",
    "                # if i == 20000:\n",
    "                #     print(each, cnt)\n",
    "        return 0\n",
    "                # dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x : int, fa : int) -> int:\n",
    "            cnt = nums[x]\n",
    "            for e in g[x]:\n",
    "                if e != fa:\n",
    "                    cnt += dfs(e, x)\n",
    "            if cnt == target:\n",
    "                return 0\n",
    "            return cnt\n",
    "\n",
    "        tot = sum(nums)\n",
    "        for i in range(n, 1, -1):\n",
    "            if tot % i != 0: continue\n",
    "            target = tot / i\n",
    "            if dfs(0, -1) == 0:\n",
    "                return i - 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in nums]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> int:\n",
    "            s = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    res = dfs(y, x)\n",
    "                    if res < 0: return -1\n",
    "                    s += res\n",
    "            if s > target: return -1\n",
    "            return s if s < target else 0\n",
    "\n",
    "        total = sum(nums)\n",
    "        for i in range(total // max(nums), 1, -1):\n",
    "            if total % i == 0:\n",
    "                target = total // i\n",
    "                if dfs(0, -1) == 0: return i - 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        def dfs(u, fa, t):\n",
    "            s = nums[u]\n",
    "            for ne in g[u]:\n",
    "                if ne == fa: continue\n",
    "                son = dfs(ne, u, t)\n",
    "                if son < 0: return -1\n",
    "                s += son\n",
    "            if s > t: return -1\n",
    "            return s if s < t else 0\n",
    "\n",
    "        tot = sum(nums)\n",
    "        for i in range(tot // max(nums), 1, -1):\n",
    "            if tot % i == 0:\n",
    "                t = tot // i\n",
    "                if dfs(0, -1, t) == 0: return i - 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, a: List[int], e: List[List[int]]) -> int:\n",
    "        n=len(a)\n",
    "        tree=[[] for i in range(n)]\n",
    "        for i,j in e:\n",
    "            tree[i].append(j)\n",
    "            tree[j].append(i)\n",
    "        def dfs(r,f,v):\n",
    "            ans=a[r]\n",
    "            for i in tree[r]:\n",
    "                if i!=f:\n",
    "                    res=dfs(i,r,v)\n",
    "                    if res<0:\n",
    "                        return -1\n",
    "                    ans+=res\n",
    "            return ans if ans<v else 0 if ans==v else -1\n",
    "        s=sum(a)\n",
    "        ans=0\n",
    "        for i in range(2,n+1):\n",
    "            if s%i==0:\n",
    "                res=dfs(0,-1,s//i)\n",
    "                if res==0:\n",
    "                    ans=i-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n=len(nums)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x:int,fa:int):\n",
    "            s=nums[x]\n",
    "            nonlocal cnt\n",
    "            for y in  g[x]:\n",
    "                if y!=fa:\n",
    "                    s=s+dfs(y,x)\n",
    "            if s==target:\n",
    "                cnt+=1\n",
    "                return 0\n",
    "            elif s<target:\n",
    "                return s\n",
    "            else:\n",
    "                return -1\n",
    "            \n",
    "        total=sum(nums)\n",
    "        for i in range(total//max(nums),1,-1):\n",
    "            cnt=0\n",
    "            if total%i==0:\n",
    "                target=total//i \n",
    "                dfs(0,-1)\n",
    "                if cnt==i:\n",
    "                    return i-1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        graph = [[] for _ in range(n)]\n",
    "        res = 0\n",
    "        for fr, to in edges:\n",
    "            graph[fr].append(to)\n",
    "            graph[to].append(fr)\n",
    "        \n",
    "        def dfs(root, t, p):\n",
    "            nonlocal res\n",
    "            v = nums[root]\n",
    "            for r in graph[root]:\n",
    "                if r != p:\n",
    "                    v += dfs(r, t, root)\n",
    "            if v == t:\n",
    "                res += 1\n",
    "                v = 0\n",
    "            if v > t:\n",
    "                res = -inf\n",
    "            return v\n",
    "\n",
    "        ans = 0\n",
    "        st = -1\n",
    "        for i in range(n):\n",
    "            if len(graph[i]) == 1:\n",
    "                st = i\n",
    "                break\n",
    "        a = []\n",
    "        s = sum(nums)\n",
    "        for i in range(min(nums), s+1):\n",
    "            if s % i == 0:\n",
    "                a.append(i)\n",
    "        for s in a:\n",
    "            res = 0\n",
    "            dfs(st, s, -1)\n",
    "            ans = max(ans, res-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)] \n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        def dfs(u: int, fa: int, a: int) -> int:\n",
    "            val = nums[u]\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                # 获取子树的和\n",
    "                val += dfs(v, u, a)\n",
    "            if val == a:\n",
    "                return 0\n",
    "            return val\n",
    "        s, m = sum(nums), max(nums)\n",
    "        # 最多切分的个数\n",
    "        cnt = s // m\n",
    "        for i in range(cnt, 1, -1):\n",
    "            if s % i != 0:\n",
    "                continue\n",
    "            if dfs(0, -1, s // i) == 0:\n",
    "                return i - 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        def check(node, par, target):\n",
    "            s = 0\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                sub = check(nei, node, target)\n",
    "                if sub == - 1:\n",
    "                    return - 1\n",
    "                s += sub \n",
    "            s += nums[node]\n",
    "            if s > target:\n",
    "                return - 1\n",
    "            if s == target:\n",
    "                return 0 \n",
    "            return s \n",
    "        s = sum(nums)\n",
    "        for i in range(1, s + 1):\n",
    "            if s % i:\n",
    "                continue \n",
    "            if check(0, - 1, i) == 0:\n",
    "                return s // i - 1 \n",
    "        return 0\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(cur,pre):\n",
    "            f = nums[cur]\n",
    "            for nxt in g[cur]:\n",
    "                if nxt != pre:\n",
    "                    res = dfs(nxt,cur)\n",
    "                    if res < 0:\n",
    "                        return -1\n",
    "                    f += res\n",
    "            if f > target:\n",
    "                return -1\n",
    "            elif f < target:\n",
    "                return f\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        t = sum(nums)\n",
    "        for i in range(t//max(nums),1,-1):\n",
    "            if t % i ==0:\n",
    "                target = t // i\n",
    "                if dfs(0,-1) == 0:\n",
    "                    return i - 1\n",
    "        return 0\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
